package com.heima.leetcode.practice;

/**
 * leetcode 704. 二分查找, 无重复元素
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/6 21:40
 */
public class E704 {

    /**
     * <h3>方法一：基本的二分查找</h3>
     * @param nums 数组
     * @param target 目标值
     * @return 找到的下标，未找到返回-1
     */
    public int search1(int[] nums, int target) {
        int left = 0; // 左边界，包含
        int right = nums.length - 1; // 右边界，包含
        while (left <= right){ // left == right的时候说明范围内还有元素，有可能是target
            int median = (left + right) >>> 1; // 避免溢出
            if (nums[median] < target){
                left = median + 1;
            } else if (target < nums[median]) {
                right = median - 1;
            } else {
                return median;
            }
        }
        return -1;
    }

    /**
     * <h3>方法二：递归版本基本的二分查找</h3>
     * @param nums 数组
     * @param target 目标值
     * @return 找到的下标，未找到返回-1
     */
    public int search2(int[] nums, int target) {
        return search2(nums, target, 0, nums.length - 1);
    }

    /**
     * 递归版本基本的二分查找实现
     * @param nums 数组
     * @param target 目标值
     * @param left 左边界（包含）
     * @param right 右边界（包含）
     * @return 找到的下标，未找到返回-1
     */
    private int search2(int[] nums, int target, int left, int right) {
        // 递归结束条件：left > right或者找到了目标值
        if (left > right){
            return -1;
        }
        // 递的时候缩小范围
        // 归的时候返回找到的下标
        int median = (left + right) >>> 1;
        if (nums[median] < target){
            return search2(nums, target, median + 1, right);
        } else if (target < nums[median]) {
            return search2(nums, target, left, median - 1);
        } else {
            return median;
        }
    }

    /**
     * <h3>方法三：改动版的二分查找</h3>
     * @param nums 数组
     * @param target 目标值
     * @return 找到的下标，未找到返回-1
     */
    public int search3(int[] nums, int target) {
        int left = 0; // 左边界，包含
        int right = nums.length; // 右边界，不包含
        while (left < right){
            int median = (left + right - 1) >>> 1; // 这里减一不减一没有影响，median都会落在有效范围内
            if (nums[median] < target){
                left = median + 1; // left在范围内
            } else if (target < nums[median]) {
                right = median; // right在范围外
            } else {
                return median;
            }
        }
        return -1;
    }

    /**
     * <h3>方法四：平衡版的二分查找</h3>
     * @param nums 数组
     * @param target 目标值
     * @return 找到的下标，未找到返回-1
     */
    public int search4(int[] nums, int target) {
        int left = 0; // 左边界，包含
        int right = nums.length; // 右边界，不包含
        while (right - left != 1){
            int median = (left + right) >>> 1;
            if (nums[median] <= target){
                left = median; // 不要加1，否则会影响循环条件，等于条件让left停在median
            } else {
                right = median;
            }
        }
        return nums[left] == target ? left : -1;
    }
}
